package me.algo.tree;

import java.util.LinkedList;
import java.util.Objects;

/**
 * @author guozheng
 * @date 2024/4/19
 */
public class T9 {
    public static void main(String[] args) {

    }

    /**
     * 117. 填充每个节点的下一个右侧节点指针 II
     * 层遍历  每层从右往左
     * @param root
     * @return
     */
    public Node connect(Node root) {
        if (Objects.isNull(root)) {
            return root;
        }
        LinkedList<Node> que = new LinkedList<>();
        que.addLast(root);
        while (!que.isEmpty()) {
            int size = que.size();
            Node levelCur = null;
            while (size > 0) {
                size--;
                Node node = que.removeFirst();
                node.next = levelCur;
                levelCur = node;
                if (node.right != null) {
                    que.addLast(node.right);
                }
                if (node.left != null) {
                    que.addLast(node.left);
                }
            }
        }
        return root;
    }


    static class Node {
        public int val;
        public Node left;
        public Node right;
        public Node next;

        public Node() {}

        public Node(int val) {
            this.val = val;
        }

        public Node(int val, Node left, Node right, Node next) {
            this.val = val;
            this.left = left;
            this.right = right;
            this.next = next;
        }
    }
}
